package arithmetic.any;

import com.dycong.common.leetcode.ds.DLinkedNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 作用描述: hashMap 与 链表组成 Lru 缓存
 *
 * @author dycong
 * @date 2019/12/18 9:10
 */
public class LruCache {

    private int capacity;
    private int count;
    private DLinkedNode head, tail;

    private Map<String, DLinkedNode> cache = new HashMap<>(16);

    public LruCache(int capacity) {
        this.capacity = capacity;
        count = 0;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.post = tail;
        tail.pre = head;
    }


    private void removeNode(DLinkedNode node) {
        if (node == head || node == tail) return;

        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;

        pre.post = post;
        post.pre = pre;
    }

    private void addHeadNode(DLinkedNode node) {
        DLinkedNode originNode = head.post;

        head.post = node;
        node.pre = head;

        originNode.pre = node;
        node.post = originNode;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addHeadNode(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode originNode = tail.pre;
        if (originNode == head) return null;
        removeNode(originNode);
        return originNode;
    }

    public int put(String key, int val) {
        DLinkedNode node = cache.get(key);

        if (node == null) {
            node = new DLinkedNode(key, val);
            cache.put(key, node);
            addHeadNode(node);
            count++;

            if (count > capacity) {
                DLinkedNode tailNode = removeTail();
                if (null != tailNode) {
                    cache.remove(tailNode.key);
                }
            }
            return -1;
        } else {
            int originVal = node.value;
            moveToHead(node);
            node.value = val;
            // cache.put(key, node);  简单替换即可不需要重新put
            return originVal;
        }
    }

    public int get(String key) {
        DLinkedNode node = cache.get(key);
        if (null == node) {
            return -1;
        }

        moveToHead(node);
        return node.value;
    }

    public static void main(String[] args) {
        com.dycong.common.leetcode.LruCache lruCache = new com.dycong.common.leetcode.LruCache(3);

        for (int i = 0; i < 10; i++) {
            lruCache.put("" + i, i);
            System.out.println("i:" + i + "   cache:" + lruCache.toString());
        }
        System.out.print(lruCache.get("7"));
        System.out.println("  cache:" + lruCache.toString());
    }
}
